using System.Collections.Generic;
using UnityEngine;


namespace Super
{
	/// <summary>
	/// 二叉搜索树，相比于二叉树拥有左节点值小于根节点，根节点值小于右节点的特点
	/// 可以进行更快速的查找，插入，删除操作
	/// 但是最坏的情况下和二叉树效果一样
	/// </summary>
	/// <typeparam name="T"></typeparam>
	public class BST<T> : BinaryTree<T> where T : IComparable<T>
	{
		public BST()
		{

		}
		public BST(T value)
		{
			Insert(value);
		}
		public BST(List<T> values)
		{
			foreach (T value in values)
				Insert(value);
		}

		/// <summary>
		/// 插入值，新增节点
		/// 保证左节点值小于根节点，根节点值小于右节点
		/// </summary>
		/// <param name="value"></param>
		public override void Insert(T value)
		{
			root = InsertRec(root, value);
		}

		private BinaryTreeNode<T> InsertRec(BinaryTreeNode<T> root, T value)
		{
			if (root == null)
			{
				root = new BinaryTreeNode<T>(value);
				return root;
			}

			if (root.value.CompareTo(value) == 1)
			{
				if (root.left == null)
				{
					root.left = new BinaryTreeNode<T>(value);
				}
				else
				{
					InsertRec(root.left, value);
				}
			}
			else
			{
				if (root.right == null)
				{
					root.right = new BinaryTreeNode<T>(value);
				}
				else
				{
					InsertRec(root.right, value);
				}
			}

			UpdateHeight(root);
			return root;
		}

		/// <summary>
		/// 平衡二叉树查找：二分查找
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		public override BinaryTreeNode<T> Find(T value)
		{
			if (root == null)
				return null;
			return FindRec(root, value);
		}

		private BinaryTreeNode<T> FindRec(BinaryTreeNode<T> root, T value)
		{
			if (root == null)
				return null;

			if (root.value.CompareTo(value) == 0)
				return root;
			else if (root.value.CompareTo(value) == 1)
				return FindRec(root.left, value);
			else
				return FindRec(root.right, value);
		}

		/// <summary>
		/// 删除节点
		/// 若节点是叶子节点，直接删除
		/// 若节点只有左子树，或右子树，返回对应的子树
		/// 否则，从节点的右子树节点开始获取值最小的节点与当前节点值交换
		/// 更新节点高度
		/// </summary>
		/// <param name="value"></param>
		public override void Delete(T value)
		{
			root = Delete(root, value);
		}

		protected virtual BinaryTreeNode<T> Delete(BinaryTreeNode<T> node, T value)
		{
			if (node == null)
			{
				return null;
			}

			if (node.value.CompareTo(value) == 1)
			{
				node.left = Delete(node.left, value);
			}
			else if (node.value.CompareTo(value) == -1)
			{
				node.right = Delete(node.right, value);
			}
			else
			{
				if (node.left == null && node.right == null)
				{
					return null;
				}
				else if (node.left == null)
				{
					return node.right;
				}
				else if (node.right == null)
				{
					return node.left;
				}
				else
				{
					BinaryTreeNode<T> minNode = FindMin(node.right);
					node.value = minNode.value;
					node.right = Delete(node.right, minNode.value);
				}
			}

			node.height = Mathf.Max(Height(node.left), Height(node.right)) + 1;
			return node;
		}

		/// <summary>
		/// 查找从节点开始值最小的节点
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public BinaryTreeNode<T> FindMin(BinaryTreeNode<T> node)
		{
			BinaryTreeNode<T> minNode = node;
			while (minNode.left != null)
			{
				minNode = minNode.left;
			}
			return minNode;
		}

		/// <summary>
		/// 查找从节点开始值最大的节点
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public BinaryTreeNode<T> FindMax(BinaryTreeNode<T> node)
		{
			BinaryTreeNode<T> maxNode = node;
			while (maxNode.right != null)
			{
				maxNode = maxNode.right;
			}
			return maxNode;
		}

	}

}
